如何理解二分查找？生活中还能用来设计骗局？

版权声明：本文为苦逼的码农原创。未经同意禁止任何形式转载，特别是那些复制粘贴到别的平台的，否则，必定追究。欢迎大家多多转发，谢谢。

来源公众号：苦逼的码农

作者：帅地

期末考要来了，最近小秋正在从零开始复习算法相关知识….

一道简单的算法题

帅地：听说你最近正在临时饱佛教复习各种算法？

小秋：对啊，算法太难了，把我头都搞大了，不过，感觉自己复习的好像还不错。

帅地：那我找一道简单的题考考你？

小秋：好啊，好啊，正好可以试试水。

帅地：给你一个有序数组，例如

然后我给出一个元素 target，你返回它对应数组的下标，如果数组中不存在这个元素的话，则返回 -1。例如

1、我给出 target = 18，则你需要返回 5。

2、我给出 target = 1，你需要返回 0。

3、我给出 target = 10，由于数组中不存在 10 这个元素，所以你需要返回 -1。

小秋：这也太简单了吧，我从左到右遍历数组所有元素，就可以找出来了。

帅地：这是一种方法，不过你这种方法的时间复杂度为 O(n)，有没有时间复杂度上更小的方法呢？

小秋：那我可以采用哈希表来存储，把数组元素作为 key，对应的下标作为 value，这样的话，以后需要查找某个元素了，我就可以在时间复杂度为 O(1) 找到对应的元素下标了。

帅地：你这种方法，需要用哈希表来存放元素，虽然时间复杂度为 O(1)，但是空间复杂度为 O(n) 了，你能不能在时间复杂度和空间复杂度折中一下，找出更加优美的方法呢？

小秋：好像，，目前没啥思路。

神速的二分查找

帅地：你听说过二分查找吗？

小秋：二分查找？什么鬼？

帅地：这道题就可以用二分查找来解决了，我来给你讲讲吧。

小秋：好啊，好啊。

帅地：其实呢，对于这道题，由于数组是有序的，我们每次在查找的时候，可以直接从中间元素开始比较，例如我们要查找 target = 10，这个元素，我们把 target 与数组中间的那个元素 15，进行比较。

（1）如果 target 比 15 小，那么 15 以及 15 右边的所有元素一定比 target 大，所以 target 只能存在于 15 的左边元素中。

（2）如果 target 比 15 大，那么 15 以及 15 左边的所有元素一定比 target 小，所以 target 只能存在于 15 的右边元素中。

（3）如果 target 与 15 相等，则直接把 15 对应的下标返回即可。

在这个例子中，target = 10 比 15 小，所以 target 只可能存在于 15 的左边元素中

接下来我们只需要在左半部分查找这个元素就可以了，右半部分的元素可以不用管了，你看，通过这种方式，只需要一次比较，我们就可以把查找的范围缩小了一半。

接着我们继续把 target 与中间元素比较，这时候中间元素是 5，15比 5 大，所以 target 只可能存在于 5 右边的元素中

接下来我们继续查找，这时中间元素是 10，和 target 相等，所以直接把 10 的下标 index = 2 返回。

二分查找的本质

帅地：小秋啊，这种每次都从中间元素开始比较，并且一次比较后就能把查找范围缩小一半的方法，就叫做二分查找了，这种二分查找的时间复杂度是 O(logn)，空间复杂度是 O(1)，可以说非常快的了。

小秋：那什么情况下可以使用二分查找这种方法呢？

帅地：要使用二分查找，给的数据需要具备两个基本的特性

（1）给的数据是有序的。

（2）给的数据支持随机访问。

小秋：什么是随机访问呢？

帅地：例如像数组就支持随机访问了，例如你要访问第 5 个元素，那么你就可以用下标为 4，即 arr[4] 来快速访问第五个元素了。而链表就不支持随机访问了，例如你要访问链表的第 5 个元素，你无法像数组那样，直接用下标来定位，只能从链表头部一个一个遍历到第五个。

小秋：哦，我知道了，只有支持随机访问，我们才能根据数组最左边和最右边的下标，直接定位到数组的中间元素。

帅地：是的，那你可以根据刚才那道题写一下代码吗？

小秋：没问题。

    public static int binarySearch(int target, int[] arr) {
        // 数组最左边元素下标
        int left = 0;
        // 数组最右边元素下标
        int right = arr.length - 1;
        while (left <= right) {
            // 中间元素下标
            int mid = (right + left) / 2;
            if (arr[mid] > target) {
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                return arr[mid];
            }
        }
        return -1;
    }

90% 的人都会犯的错误

帅地：你写的基本正确，不过有个小问题，就是算中间元素下标那里

mid = (left + right) / 2;

你这种方法有时候会产生溢出的哦。例如，我们知道 int 整数的最大值大概是 2^31 - 1 大概为 21 亿。而 left 和 right 这两个数相加是有可能超过 21 亿的，例如 left = 12亿，right = 13 亿。这个时候，两个数的和超过了最大值，就会产生溢出了。

小秋：那该怎么写？

帅地：正确的写法应该是这样的

mid = left + (right - left) / 2;

这样，就能保存不会出现溢出的情况了。

二分查找在生活中的骗局

帅地：其实在我们的生活中，二分查找也是有挺多应用的，例如用二分查找来做坏事。

小秋：坏事？可以给我举例看看吗？

帅地：有时候临近一些比赛了，例如全世界性的足球大赛，有时候我们会收到一些邮件，有人谎称他会神预算，例如今天是德国和法国比赛，他会跟你说一定是德国胜，然后跟另外一部分人今天一定是法国胜。

而德国和法国，总有一个人会胜，那么他可以跟 10000人说德国胜，10000人说法国胜。我们假如是德国胜了，那么在 10000 人看来它的预算是正确的。

接着德国和俄罗斯比赛，它会在那 10000 人中，跟 5000人说德国胜，5000人说俄罗斯胜。那么在 5000 看来它的预算还是正确的….

就这样，每次它都从被他预算正确的那一部分人继续吹他会神预算，那么在有些人看来，他果真连续预算正确，这个时候，这些人可能就会认为，他真的有神预算的能力，于是，可能就会相信它说的话了，进而就会被他所欺骗。

小秋：虽然我没收到这类邮件，但是我经常收到一些六合彩的短信

帅地：是的，这些，就是利用的二分查找的思想了。

二分查找？没有你想的那么简单

帅地：小秋啊，刚才给你讲的那道题，可以说是最简单的了，其实，对于二分查找，有很多变形题的，往往不会那么简单。

小秋：那你可以给我出几道，看我能不能现学现卖。

帅地：那我给你两道题吧。

1、实现 pow(x, n)函数：即计算 x 的 n 次方。不准使用我之前给你讲的位运算：【算法技巧】位运算装逼指南。

2、搜索选择排序数组：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

这两道题，可以说是中等难度的变形题了，跟我说说怎么做？

小秋：这….，我才刚学完，能不能给我点时间让让想想？

帅地：大概多长呢？

小秋：不长，两天时间就可以了。

帅地：两天 还不长…… 好吧，那两天后见。

总结

这次主要讲解了二分查找的基本思想以及生活在的例子，二分查找思想虽然不难，不过却有很多不容易的题，后面的问题，如果小秋没做出来，我就下次给大家讲解。如果小秋做出来的，我们就来听听他怎么做的，敬请期待。

你可能会喜欢